#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define InitSize 100
#define StepSize 10
#define id_opnd 1
#define id_optr 2
char OP[7] = {'+','-','*','/','(',')','#'};
char tnumber[100];
typedef struct SqStack_OPND
{
	double* base;
	double* top;
	int stacksize;
	int id;
}SqStack_OPND;

typedef struct SqStack_OPTR
{
	char* base;
	char* top;
	int stacksize;
	int id;
}SqStack_OPTR;


int InOP(char* OP,char c)
{
	for(int i = 0;i < 7;i++)
	{
		if(c == OP[i])
		{
			return 1;	
		}	
	}
	return 0;	
} 

int initStack_OPND(SqStack_OPND* S)
{
	S->base = (double*)malloc(sizeof(double)*InitSize);
	if(S->base == NULL)
	{
		S->base = NULL;
		S->top = NULL;
		S->stacksize = -1;
		return 0;
	}
	S->top = S->base;
	S->stacksize = InitSize;
	S->id = id_opnd;
	return 1;
}
int initStack_OPTR(SqStack_OPTR* S)
{
	S->base = (char*)malloc(sizeof(char)*InitSize);
	if(S->base == NULL)
	{
		S->base = NULL;
		S->top = NULL;
		S->stacksize = -1;
		return 0;
	}
	S->top = S->base;
	S->stacksize = InitSize;
	S->id = id_optr;
	return 1;
}

int StackLength(void* s,int id)
{
	if(id == id_opnd)
	{
		SqStack_OPND* S = (SqStack_OPND*)s;
		if(S->base == NULL)
		{
			return -1;
		}
		return S->top-S->base;
	}
	if(id == id_optr)
	{
		SqStack_OPTR* S = (SqStack_OPTR*)s;
		if(S->base == NULL)
		{
			return -1;
		}
		return S->top-S->base;
	}
	return -1;
}

int PushStack_OPND(SqStack_OPND* S,double e)
{
	if(S->base == NULL)
	{
		puts("\nOPND is not exist！");
		return 0;
	}
	if(StackLength(S,S->id) >= S->stacksize)
	{
		S->base = (double*)realloc(S->base,sizeof(double)*(S->stacksize+StepSize));
		if(S->base != NULL)
		{
			S->top = S->base+S->stacksize;
			S->stacksize = S->stacksize+StepSize;
			*(S->top) = e;
			(S->top)++;
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else
	{
		*(S->top) = e;
		(S->top)++;
		return 1;
	}
}
int PushStack_OPTR(SqStack_OPTR* S,char e)
{
	if(S->base == NULL)
	{
		puts("\nOPND is not exist！");
		return 0;
	}
	if(StackLength(S,S->id) >= S->stacksize)
	{
		S->base = (char*)realloc(S->base,sizeof(char)*(S->stacksize+StepSize));
		if(S->base != NULL)
		{
			S->top = S->base+S->stacksize;
			S->stacksize = S->stacksize+StepSize;
			*(S->top) = e;
			(S->top)++;
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else
	{
		*(S->top) = e;
		(S->top)++;
		return 1;
	}
}
int PopStack_OPND(SqStack_OPND* S,double* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		(S->top)--;
		*e = *(S->top);
		return 1;
	}
}
int PopStack_OPTR(SqStack_OPTR* S,char* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		(S->top)--;
		*e = *(S->top);
		return 1;
	}
}

int GetTopStack_OPND(SqStack_OPND* S,double* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		*e = *(S->top - 1);
		return 1;
	}
}
int GetTopStack_OPTR(SqStack_OPTR* S,char* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		*e = *(S->top - 1);
		//printf("*e = %c",*e);
		return 1;
	}
}

int TraverseStack_OPND(SqStack_OPND* S)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		printf("栈顶指针----->0：空<-----栈底指针"); 
		return 0;
	}
	double* p;
	printf("栈顶指针----->%d\n",StackLength(S,S->id)); 
	for(p = S->top;p - S->base - 1 != -1;p--)
	{
		if((p - S->base - 1) == 0)
		{
			printf("栈底指针----->0:%f\n",(S->base)[0]);
		}
		else
		{
			printf("              %d:%f\n",p - S->base - 1,(S->base)[p - S->base - 1]);
		}
	}
	return 1;
}
int TraverseStack_OPTR(SqStack_OPTR* S)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		printf("栈顶指针----->0：空<-----栈底指针"); 
		return 0;
	}
	char* p;
	printf("栈顶指针----->%d\n",StackLength(S,S->id)); 
	for(p = S->top;p - S->base - 1 != -1;p--)
	{
		if((p - S->base - 1) == 0)
		{
			printf("栈底指针----->0:%c\n",(S->base)[0]);
		}
		else
		{
			printf("              %d:%c\n",p - S->base - 1,(S->base)[p - S->base - 1]);
		}
	}
	return 1;
}
double Operate(double a,char op,double b)
{
	switch(op)
	{
		case '+':return a + b;
		case '-':return a - b;
		case '*':return a*b;
		case '/':
			if(fabs(b-0) <= 0.0000001)
			{
				return -2147483648.2147;
			}
			else
			{
				//printf("\na/b = %f\n",a/b);
				return a/b; 
				
			}
		default:return -2147483648.2147;
	}
}
char Precede(char t1,char t2)
{
	switch(t1)
	{
		case '+':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '-':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '*':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '>';
				case '/':return '>';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '/':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '>';
				case '/':return '>';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '(':
			switch(t2)
			{
				case '+':return '<';
				case '-':return '<';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '=';
				case '#':return '@';
			}
		case ')':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '>';
				case '/':return '>';
				case '(':return '@';
				case ')':return '>';
				case '#':return '>';
			}
		case '#':
			switch(t2)
			{
				case '+':return '<';
				case '-':return '<';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '@';
				case '#':return '=';
			}	
		default:return '@';
	}
}
double EvaluateExpression()
{
	SqStack_OPND opnd;
	SqStack_OPTR optr;
	
	int n[1] = {0};
	int k = 0;
	char ch;
	char c;

	
	double pop_a;
	double pop_b;
	char theta;
	char pop_ch;
	
	double pop_return;
	
	initStack_OPTR(&optr);PushStack_OPTR(&optr,'#');
	initStack_OPND(&opnd);scanf("%c",&c);
	
	while(c != '#' || (GetTopStack_OPTR(&optr,&ch),ch != '#'))  
	{
		if(InOP(OP,c) == 0)
		{
			if((c >= '0' && c <= '9') || c == '.')
			{
				n[0] = 0;
				tnumber[k++] = c;
			}
			//printf("n[0] = %d,n[1] = %d,i-1 = %d\n",n[0],n[1],i-1);
			//PushStack_OPND(&opnd,c-48);
			//TraverseStack_OPND(&opnd);
			//TraverseStack_OPTR(&optr);
			//puts("-------------------");
			c = getchar();
		}
		else
		{
			//printf("[c = %c,n[0] = %d]",c,n[0]);
			if(n[0] == 0)
			{
				tnumber[k] = '\0';
				PushStack_OPND(&opnd,atof(tnumber));
				n[0] = 1;
				k = 0;
				TraverseStack_OPND(&opnd);
				TraverseStack_OPTR(&optr);
			}

			GetTopStack_OPTR(&optr,&ch);
			switch(Precede(ch,c))
			{
				case '<':
					PushStack_OPTR(&optr,c);
					TraverseStack_OPND(&opnd);
					TraverseStack_OPTR(&optr);
					puts("-------------------");
					c = getchar();
					break;
				case '=':
					PopStack_OPTR(&optr,&pop_ch);
					TraverseStack_OPND(&opnd);
					TraverseStack_OPTR(&optr);
					puts("-------------------");
					c = getchar();
					break;
				case '>':
					PopStack_OPTR(&optr,&theta);
					PopStack_OPND(&opnd,&pop_a);
					PopStack_OPND(&opnd,&pop_b);
					
					if(Operate(pop_b,theta,pop_a) == -2147483648.2147)
					{
						return -2147483648.2147;
					}
					
					PushStack_OPND(&opnd,Operate(pop_b,theta,pop_a));
					TraverseStack_OPND(&opnd);
					TraverseStack_OPTR(&optr);
					puts("-------------------");
					break; 
			}
		}
	}
	GetTopStack_OPND(&opnd,&pop_return);
	free(opnd.base);
	free(optr.base);
	return pop_return;
}

int main()
{
	puts("【输入表达式以#结尾】其中运算符['+','-','*','/','(',')','#']:");
	puts("【参与运算的数字只能是整数或浮点数】"); 
	puts("【例子】：36.8+69-14.5*(25.7-(45.4/2))-3.9#"); 
    printf("计算结果：%f\n",EvaluateExpression());
	system("pause");
	return 0;
}